package org.indolphin.algorithm.sort;

/**
 * 基数排序（桶排序）
 * TODO 不适用于数组中存在负数的情况
 * @author hongyan
 */
public class RadixSort {

    public void sort(int[] data) {

        int max = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] > max) {
                max = data[i];
            }
        }
        int n = (max + "").length();

        int[][] bucket = new int[10][data.length];
        // 记录bucket中每个桶放入的数据个数
        int[] bucketElementCounts = new int[10];


        for (int i = 0, m = 1; i < n; i++, m *= 10) {
            for (int j = 0; j < data.length; j++) {
                int digitOfElement = data[j] / m % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = data[j];
                bucketElementCounts[digitOfElement]++;
            }

            // 将桶中的数据拷贝回data
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    data[index] = bucket[k][l];
                    index++;
                }
                bucketElementCounts[k] = 0;
            }
        }


    }
}
